{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Jump Game VI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #queue #array #dynamic-programming #monotonic-queue #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #队列 #数组 #动态规划 #单调队列 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxResult"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #跳跃游戏 VI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> 和一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>一开始你在下标 <code>0</code> 处。每一步，你最多可以往前跳 <code>k</code> 步，但你不能跳出数组的边界。也就是说，你可以从下标 <code>i</code> 跳到 <code>[i + 1， min(n - 1, i + k)]</code> <strong>包含</strong> 两个端点的任意位置。</p>\n",
    "\n",
    "<p>你的目标是到达数组最后一个位置（下标为 <code>n - 1</code> ），你的 <strong>得分</strong> 为经过的所有数字之和。</p>\n",
    "\n",
    "<p>请你返回你能得到的 <strong>最大得分</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [<strong>1</strong>,<strong>-1</strong>,-2,<strong>4</strong>,-7,<strong>3</strong>], k = 2\n",
    "<b>输出：</b>7\n",
    "<b>解释：</b>你可以选择子序列 [1,-1,4,3] （上面加粗的数字），和为 7 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [<strong>10</strong>,-5,-2,<strong>4</strong>,0,<strong>3</strong>], k = 3\n",
    "<b>输出：</b>17\n",
    "<b>解释：</b>你可以选择子序列 [10,4,3] （上面加粗数字），和为 17 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,-5,-20,4,-1,3,-6,-3], k = 2\n",
    "<b>输出：</b>0\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li> <code>1 <= nums.length, k <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [jump-game-vi](https://leetcode.cn/problems/jump-game-vi/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [jump-game-vi](https://leetcode.cn/problems/jump-game-vi/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,-1,-2,4,-7,3]\\n2', '[10,-5,-2,4,0,3]\\n3', '[1,-5,-20,4,-1,3,-6,-3]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        q = deque([0])\n",
    "        for i in range(1,len(nums)):\n",
    "            if q[0] < i-k: q.popleft()\n",
    "            nums[i] += nums[q[0]]\n",
    "            while q and nums[q[-1]] <= nums[i]: q.pop()\n",
    "            q.append(i)\n",
    "        return nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) <= 2:\n",
    "            return sum(nums)\n",
    "        if k == 1:\n",
    "            return sum(nums)\n",
    "        if k >= len(nums):\n",
    "            return nums[0]+nums[-1]+sum(filter(lambda x: x>0, nums[1:-1]))\n",
    "        q = deque([(nums[0], 0)])\n",
    "        for i, n in enumerate(nums[1:], 1):\n",
    "            while q and q[0][1] < i-k:\n",
    "                q.popleft()\n",
    "            x = q[0][0] + n\n",
    "            while q and q[-1][0] < x:\n",
    "                q.pop()\n",
    "            q.append((x, i))\n",
    "            # print(q)\n",
    "        return q[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        stack = collections.deque([(nums[0], 0)])\n",
    "        ans = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            ans = nums[i] + stack[0][0]\n",
    "            while stack and ans >= stack[-1][0]:\n",
    "                stack.pop()\n",
    "            stack.append((ans, i))\n",
    "            while i >= stack[0][1] + k:\n",
    "                stack.popleft()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return sum(nums)\n",
    "\n",
    "        q = deque([(nums[0], 0)])\n",
    "        for i, n in enumerate(nums[1:], 1):\n",
    "            while q and q[0][1] < i-k:\n",
    "                q.popleft()\n",
    "            x = q[0][0] + n\n",
    "            while q and q[-1][0] < x:\n",
    "                q.pop()\n",
    "            q.append((x, i))\n",
    "            # print(q)\n",
    "        return q[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        q, f, s, e = [0]*len(nums), [0]*len(nums), 0, 1\n",
    "        f[0] = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            while s<e and q[s]+k<i : s+=1\n",
    "            f[i] = f[q[s]]+nums[i]\n",
    "            while s<e and f[q[e-1]]<f[i] : e-=1\n",
    "            q[e] = i\n",
    "            e+=1\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        que=deque()\n",
    "        for i,x in enumerate(nums):\n",
    "            while que and i-que[0][0]>k:\n",
    "                que.popleft()\n",
    "            if len(que)==0:\n",
    "                ans=x\n",
    "            else:\n",
    "                ans=que[0][1]+x\n",
    "            while que and ans>que[-1][1]:\n",
    "                que.pop()\n",
    "            que.append([i,ans])\n",
    "        return que.pop()[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        stack=[[nums[0],0]]\n",
    "\n",
    "        res=nums[0]\n",
    "        for i in range(1,n):\n",
    "            while stack and i- stack[0][1]>k:\n",
    "                stack.pop(0)\n",
    "            res=nums[i]+stack[0][0]\n",
    "\n",
    "            while stack and stack[-1][0]<res:\n",
    "                stack.pop()\n",
    "            stack.append([res,i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        # 单调队列\n",
    "        n = len(nums)\n",
    "        q = deque([[nums[0], 0]])  # 单调队列\n",
    "        dp = nums[0]\n",
    "        for i in range(1, n):\n",
    "            while i - q[0][1] > k:\n",
    "                q.popleft()\n",
    "            x, j = q[0]\n",
    "            dp = x + nums[i]   # 到达 nums[i] 的最大得分\n",
    "            while q and q[-1][0] < dp:\n",
    "                q.pop()\n",
    "            q.append([dp, i])\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "\n",
    "        q = deque()\n",
    "        dp[0] = nums[0]\n",
    "        q.append(0)\n",
    "        for i in range(1, n):\n",
    "            if q and  i - q[0] > k:\n",
    "                q.popleft()\n",
    "            dp[i] = dp[q[0]] + nums[i]\n",
    "            while q and dp[q[-1]] < dp[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # print(dp)\n",
    "        return dp[n-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        from queue import deque\n",
    "        n = len(nums)\n",
    "        dp = [0] * n \n",
    "        dp[0] = nums[0]\n",
    "        que = deque()\n",
    "        que.append(0)\n",
    "        for i in range(1, n):\n",
    "            while (len(que) != 0 and i - que[0] > k):\n",
    "                que.popleft()\n",
    "            dp[i] = dp[que[0]] + nums[i]\n",
    "            while (len(que) != 0 and dp[i] >= dp[que[-1]]):\n",
    "                que.pop()\n",
    "            que.append(i)\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [nums[0]]\n",
    "        q = deque([0])\n",
    "        for i in range(1, n):\n",
    "            dp.append(nums[i] + dp[q[0]])\n",
    "            if q and i - q[0] >= k:\n",
    "                q.popleft()\n",
    "            while q and dp[q[-1]] <= dp[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class MonotonicQueue:\n",
    "    def __init__(self):\n",
    "        self.queue = collections.deque()\n",
    "\n",
    "    def push(self, n):\n",
    "        while self.queue and self.queue[-1] < n:\n",
    "            self.queue.pop()\n",
    "        self.queue.append(n)\n",
    "\n",
    "    def pop(self):\n",
    "        self.queue.popleft()\n",
    "\n",
    "    def max(self):\n",
    "        return self.queue[0]\n",
    "\n",
    "    def size(self):\n",
    "        return len(self.queue)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        window = collections.deque()\n",
    "        # 定义：到达 nums[p] 的最大分数为 dp[p]\n",
    "        dp = [float('-inf')] * n\n",
    "        # base case\n",
    "        dp[0] = nums[0]\n",
    "        window.append((dp[0], 0))\n",
    "\n",
    "        # 状态转移\n",
    "        for p in range(1, n):\n",
    "            while p - window[0][1] > k:\n",
    "                window.popleft() \n",
    "            # print(1, window.queue, window.size())\n",
    "            dp[p] = window[0][0] + nums[p]\n",
    "            # print(dp)\n",
    "\n",
    "            # print(k)\n",
    "            while window and window[-1][0] < dp[p]:\n",
    "                window.pop()\n",
    "\n",
    "            window.append((dp[p], p))\n",
    "            # print(window.queue, window.size(), nums[p], dp[p])\n",
    "\n",
    "            \n",
    "            # window.push(dp[p])\n",
    "            \n",
    "\n",
    "        return dp[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        dp = [-sys.maxsize for _ in range(len(nums))]\n",
    "        dp[0] = nums[0]\n",
    "        q =collections.deque()\n",
    "        for i in range(1, len(nums)):\n",
    "            while q and dp[q[-1]] < dp[i - 1]:\n",
    "                q.pop()\n",
    "            q.append(i - 1)\n",
    "            if q[0] <= i - 1 - k:\n",
    "                q.popleft()\n",
    "            dp[i]  = dp[q[0]] + nums[i]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        dp = nums[:]\n",
    "        delete = defaultdict(int)\n",
    "        heap = []\n",
    "        heapify(heap)\n",
    "        heappush(heap, -dp[-1])\n",
    "        length = 1\n",
    "        for i in range(len(nums)-2,-1,-1):\n",
    "            dp[i] += -heap[0]\n",
    "            heappush(heap, -dp[i])\n",
    "            length += 1\n",
    "            if length>k:\n",
    "                length -= 1\n",
    "                delete[dp[i+k]] += 1\n",
    "                while -heap[0] in delete:\n",
    "                    n = -heappop(heap)\n",
    "                    delete[n] -= 1\n",
    "                    if delete[n] == 0:\n",
    "                        del delete[n]\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        ret = 0\n",
    "        pos_indices = [0] + [i for i, num in enumerate(nums[1:-1], start=1) if num >= 0] + [len(nums)-1]\n",
    "        ret = sum(nums[i] for i in pos_indices)\n",
    "        for i in range(len(pos_indices)-1):\n",
    "            if pos_indices[i+1] - pos_indices[i] > k:\n",
    "                ret += self.findMaxSum(nums[pos_indices[i]+1:pos_indices[i+1]], k)\n",
    "\n",
    "        return ret\n",
    "\n",
    "    # DP\n",
    "    def findMaxSum(self, neg_nums: List[int], k: int) -> int:\n",
    "        neg_nums = [0] + neg_nums + [0]\n",
    "        dp = [float('-inf') for _ in range(len(neg_nums))]\n",
    "        dp[:k+1] = neg_nums[:k+1]\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            if dp[i-1] >= dp[i]:\n",
    "                if i + k <= len(dp)-1:\n",
    "                    dp[i+k] = dp[i] + neg_nums[i+k]\n",
    "                continue\n",
    "            for j in range(1, k+1):\n",
    "                if i + j <= len(dp)-1:\n",
    "                    dp[i+j] = max(dp[i+j], dp[i] + neg_nums[i+j])\n",
    "\n",
    "        print(dp)\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=1696 lang=python3\n",
    "#\n",
    "# [1696] 跳跃游戏 VI\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 带限制的子序列和，单调队列保存前k个的最大值，要想保证从零开始，初始值设置成0，其他的设置为-inf即可\n",
    "        f = [-inf] * n\n",
    "        f[0] = nums[0]\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            while q and q[0] < i - k:\n",
    "                q.popleft()\n",
    "            if q:\n",
    "                f[i] = max(f[i], f[q[0]] + nums[i])\n",
    "            while q and f[q[-1]] <= f[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        print(f)\n",
    "        return f[n-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=1696 lang=python3\n",
    "#\n",
    "# [1696] 跳跃游戏 VI\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 带限制的子序列和，单调队列保存前k个的最大值，要想保证从零开始，初始值设置成0，其他的设置为-inf即可\n",
    "        f = [0] * n\n",
    "        f[0] = nums[0]\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            while q and q[0] < i - k:\n",
    "                q.popleft()\n",
    "            if q:\n",
    "                f[i] = f[q[0]] + nums[i]\n",
    "            while q and f[q[-1]] <= f[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        print(f)\n",
    "        return f[n-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        from sortedcontainers import SortedList\n",
    "        res = [nums[0]]\n",
    "        s = SortedList()\n",
    "        s.add(nums[0])\n",
    "        for i in range(1, len(nums)):\n",
    "            res.append(s[-1]+nums[i])\n",
    "            s.add(s[-1]+nums[i])\n",
    "            if len(s)>k:\n",
    "                s.remove(res[i-k])\n",
    "            # if i<k:\n",
    "            #     res.append(max(res[:i])+nums[i])\n",
    "            # else:\n",
    "            #     res.append(max(res[i-k:i])+nums[i])\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def jump(nums, k):\n",
    "    '''\n",
    "    n = len(nums)\n",
    "    dp = [0] * n\n",
    "    dp[0] = nums[0]\n",
    "    for i in range(1, n):\n",
    "        dp[i] = min(dp[j] + nums[i] for j in range(max(0, i - k), i))\n",
    "    return dp[-1]\n",
    "    '''\n",
    "    n = len(nums)\n",
    "    dp = [0] * n\n",
    "    dp[0] = nums[0]\n",
    "    q = collections.deque([0])\n",
    "    for i in range(1, n):\n",
    "        while q and i - q[0] > k:\n",
    "            q.popleft()\n",
    "        dp[i] = dp[q[0]] + nums[i]\n",
    "        while q and dp[i] <= dp[q[-1]]:\n",
    "            q.pop()\n",
    "        q.append(i)\n",
    "    return dp[-1]\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        score = 0\n",
    "        # 因为必须经过所有的正数，所以先把他们收集起来。\n",
    "        for i, num in enumerate(nums):\n",
    "            if num > 0:\n",
    "                score += num\n",
    "                nums[i] = 0\n",
    "        # 首尾必须踩中，把他们收集起来。\n",
    "        score += nums[0] + nums[-1]\n",
    "        nums[0] = nums[-1] = 0\n",
    "        # 找到所有的段。每个段，以0开始，以0结束，中间全部是负数。\n",
    "        b = 0  # 开始位置\n",
    "        for e in range(1, n):\n",
    "            if nums[e] < 0:\n",
    "                continue\n",
    "            lst = [-nums[i] for i in range(b, e + 1)]\n",
    "            cur_score = jump(lst, k)\n",
    "            score -= cur_score\n",
    "            b = e\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        import heapq\n",
    "        stack = [-nums[0]]\n",
    "        tmp = [-nums[0]]\n",
    "        lookup = {-nums[0]:1}\n",
    "        heapq.heapify(tmp)\n",
    "        _len = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if _len<k:\n",
    "                t = heapq.heappop(tmp)\n",
    "                _len += 1\n",
    "            else:\n",
    "                t = heapq.heappop(tmp)\n",
    "                while t not in lookup:\n",
    "                    t = heapq.heappop(tmp)\n",
    "                lookup[stack[-k]] -= 1\n",
    "                if lookup[stack[-k]]==0:\n",
    "                    del lookup[stack[-k]]\n",
    "\n",
    "            stack.append(t - nums[i])\n",
    "            heapq.heappush(tmp, t)\n",
    "            heapq.heappush(tmp, stack[-1])\n",
    "            if stack[-1] not in lookup:\n",
    "                lookup[stack[-1]] = 1\n",
    "            else:\n",
    "                lookup[stack[-1]] += 1\n",
    "        return -stack[-1]\n",
    "                \n",
    "                    \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "\n",
    "        dp[0] = nums[0]\n",
    "        p1, p2 = 0, 0\n",
    "\n",
    "        m = SortedDict()\n",
    "        m[nums[p1]] = 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dp[i] = m.keys()[-1] + nums[i]\n",
    "\n",
    "            if dp[i] not in m:\n",
    "                m[dp[i]] = 1\n",
    "            else:\n",
    "                m[dp[i]] += 1\n",
    "            p2 += 1\n",
    "\n",
    "            if p2 - p1 + 1 > k:\n",
    "                m[dp[p1]] -= 1\n",
    "                if m[dp[p1]] == 0:\n",
    "                    m.pop(dp[p1])\n",
    "\n",
    "                p1 += 1\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        N = len(nums)\n",
    "        dp = []\n",
    "        heapq.heappush(dp, (0, 0))\n",
    "        tmp_max = 0\n",
    "        for ii in range(1, N):\n",
    "            t, idx = heapq.heappop(dp)\n",
    "            while idx + k <  ii:\n",
    "                t, idx = heapq.heappop(dp)\n",
    "            # print(dp,  t, idx)\n",
    "            tmp_max = t * -1 + nums[ii]\n",
    "            heapq.heappush(dp, (tmp_max *  -1, ii))\n",
    "            heapq.heappush(dp, (t, idx))\n",
    "        return tmp_max + nums[0]\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        Q = []\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            while Q and Q[0][1] < i - k:\n",
    "                heappop(Q)\n",
    "            ans = nums[i] + (-Q[0][0] if Q else 0)\n",
    "            heappush(Q, (-ans, i))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        # 如果k大的话，一个一个比较找最大就会是O(nk)，对前面k个一直维持有序就是O(nlogk)\n",
    "        # 考虑到每次只有一个元素变化，所以需要找一个有序容器，找最近k个的最大\n",
    "        # 为了实现找索引删除，只能用红黑树？\n",
    "        # 【可以不删除索引】 用最大堆弹出元素的时候看下有没有超过窗口的索引\n",
    "        # (-val, idx)\n",
    "        heap = [(0, -k)] # 这个idx必须设置为-k，否则会干扰后面的判断（如果0号是负数的话）\n",
    "        for idx, val in enumerate(nums):\n",
    "            # 弹出不在窗口内的\n",
    "            while idx - heap[0][1] > k:\n",
    "                heappop(heap)\n",
    "            # 最后输出要取反\n",
    "            if idx == len(nums) - 1:\n",
    "                return val - heap[0][0]\n",
    "            # 加入\n",
    "            heappush(heap, (heap[0][0] - val, idx))\n",
    "        \n",
    "\n",
    "           \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        heap=[(-nums[0],0)]\n",
    "        ans=nums[0]\n",
    "        for i in range(1,n):\n",
    "            while heap and i-heap[0][1]>k:\n",
    "                heapq.heappop(heap) \n",
    "            ans=nums[i]-heap[0][0]  \n",
    "            heapq.heappush(heap,(-ans,i))         \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        if not nums:\n",
    "            return 0  \n",
    "        # 初始化堆  \n",
    "        l = []\n",
    "        heapq.heappush(l, (-nums[0], 0))\n",
    "        # 开始进行优先队列操作\n",
    "        n = len(nums)\n",
    "        value = nums[0]\n",
    "        for i in range(1, n):\n",
    "            # 将出界(j<i-k)的元素出队\n",
    "            while l[0][1] < i-k:\n",
    "                heapq.heappop(l)\n",
    "            # 获取最大值\n",
    "            value = nums[i] - l[0][0]\n",
    "            heapq.heappush(l, (-value, i))\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    # def maxResult(self, nums: List[int], k: int) -> int:\n",
    "    #     dp = [0] * len(nums)\n",
    "    #     dp[0] = nums[0]\n",
    "    #     d = deque([(nums[0],0)])\n",
    "    #     for i in range(1, len(nums)):\n",
    "    #         dp[i] = nums[i] + d[0][0]\n",
    "            \n",
    "    #         while d and d[-1][0] < dp[i]:   # sliding window maximum variation\n",
    "    #             d.pop()                     # sliding window maximum variation\n",
    "    #         d.append((dp[i],i))             # sliding window maximum variation\n",
    "            \n",
    "    #         if i-k == d[0][1]:              # sliding window maximum variation\n",
    "    #             d.popleft()                 # sliding window maximum variation\n",
    "                \n",
    "    #     return dp[-1]\n",
    "\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        highestK = [(-nums[0],0)]\n",
    "        result = nums[0]  # handles case where there is just 1 itme\n",
    "        \n",
    "        for i in range(1,len(nums)):\n",
    "            while highestK[0][1] < i-k:\n",
    "                heapq.heappop(highestK)\n",
    "            result = nums[i] + -highestK[0][0]\n",
    "            heapq.heappush(highestK, (-result,i))\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        #维护当前最大值  方法1：最大堆  方法2:单调递减队列（队首）\n",
    "        n = len(nums)\n",
    "        maxHeap = []\n",
    "        heapq.heapify(maxHeap)\n",
    "        heapq.heappush(maxHeap, (-nums[0], 0) )\n",
    "        res = nums[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            while maxHeap and i - maxHeap[0][1] > k:    #index的距离太大，以后i越来越大，top()就没用了\n",
    "                heapq.heappop(maxHeap)\n",
    "            res = -maxHeap[0][0] + nums[i]\n",
    "            heapq.heappush(maxHeap, (-res, i) )         #dp的思想\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        if not nums:\n",
    "            return 0  \n",
    "        # 初始化堆  \n",
    "        l = []\n",
    "        heapq.heappush(l, (-nums[0], 0))\n",
    "        # 开始进行优先队列操作\n",
    "        n = len(nums)\n",
    "        value = nums[0]\n",
    "        for i in range(1, n):\n",
    "            # 将出界(j<i-k)的元素出队\n",
    "            while l[0][1] < i-k:\n",
    "                heapq.heappop(l)\n",
    "            # 获取最大值\n",
    "            value = nums[i] - l[0][0]\n",
    "            heapq.heappush(l, (-value, i))\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        heap=[(-nums[0],0)]\n",
    "        ret=nums[0]\n",
    "        for i in range(1,n):\n",
    "            while heap and heap[0][1]<i-k:\n",
    "                heapq.heappop(heap)\n",
    "            if i==n-1:\n",
    "                ret=-heap[0][0]+nums[i]\n",
    "            heapq.heappush(heap,(-(-heap[0][0]+nums[i]),i))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        l = len(nums)\n",
    "        hay = [(-nums[0], 0)]\n",
    "        res = -nums[0]\n",
    "\n",
    "        for i in range(1, l):\n",
    "            while i - hay[0][1] > k:\n",
    "                heappop(hay)\n",
    "            \n",
    "            res = hay[0][0]-nums[i]\n",
    "            heappush(hay, (res, i))\n",
    "\n",
    "        return -res\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    " \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        dp = [0]*len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        st = [[nums[0],0]]\n",
    "\n",
    "        for i in range(1,len(nums)):\n",
    "            while st and st[-1][1]<i-k:\n",
    "                st.pop()\n",
    "            dp[i] = dp[st[-1][1]]+nums[i]\n",
    "            bisect.insort(st,[dp[i],i])\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        res = nums[0]\n",
    "        q = queue.PriorityQueue()\n",
    "        q.put([-nums[0], 0])\n",
    "        for i in range(1, len(nums)):\n",
    "            while not q.empty():\n",
    "                tmp = q.get()\n",
    "                if tmp[-1] + k >= i:\n",
    "                    q.put(tmp)\n",
    "                    res = -tmp[0] + nums[i]\n",
    "                    break\n",
    "            q.put([-res, i])\n",
    "        return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def maxResult(self, nums: List[int], k: int) -> int:\n",
    "#         from queue import PriorityQueue\n",
    "#         ans, q = nums[0], PriorityQueue()\n",
    "#         q.put([-nums[0], 0])\n",
    "#         for i in range(1, len(nums)):\n",
    "#             while not q.empty():\n",
    "#                 top = q.get()\n",
    "#                 if i - top[-1] <= k:\n",
    "#                     q.put(top)\n",
    "#                     break\n",
    "#             ans = -top[0] + nums[i]\n",
    "#             q.put([-ans, i])\n",
    "#         return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        from queue import PriorityQueue\n",
    "        ans=nums[0]\n",
    "        q=PriorityQueue()\n",
    "        q.put([-nums[0],0])\n",
    "        for i in range(1,len(nums)):\n",
    "            while not q.empty():\n",
    "                temp=q.get()\n",
    "                if i-temp[1]<=k:\n",
    "                    q.put(temp)\n",
    "                    break\n",
    "            ans=-temp[0]+nums[i]\n",
    "            q.put([-ans,i])\n",
    "        return ans \n",
    "\n",
    "        '''\n",
    "        from queue import PriorityQueue\n",
    "        ans, q = nums[0], PriorityQueue()\n",
    "        q.put([-nums[0], 0])\n",
    "        for i in range(1, len(nums)):\n",
    "            while not q.empty():\n",
    "                top = q.get()\n",
    "                if i - top[-1] <= k:\n",
    "                    q.put(top)\n",
    "                    break\n",
    "            ans = -top[0] + nums[i]\n",
    "            q.put([-ans, i])\n",
    "        return ans\n",
    "        '''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        from queue import PriorityQueue\n",
    "        res = -nums[0]\n",
    "        heap = PriorityQueue()\n",
    "        heap.put([-nums[0], 0])\n",
    "        for i in range(1, len(nums)):\n",
    "            while heap:\n",
    "                top = heap.get()\n",
    "                if top[-1] >= i - k:\n",
    "                    heap.put([top[0] - nums[i], i])\n",
    "                    heap.put(top)\n",
    "                    res = top[0] - nums[i]\n",
    "                    break\n",
    "        return -res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        k = min(k, n - 1)\n",
    "        dp = [0] * n \n",
    "        dp[0] = nums[0]\n",
    "        d = SortedList()\n",
    "        d.add((dp[0], 0))\n",
    "        for i in range(1, k + 1):\n",
    "            dp[i] = d[-1][0] + nums[i]\n",
    "            d.add((dp[i], i))\n",
    "        for i in range(k + 1, n):\n",
    "            d.remove((dp[i - k - 1], i - k - 1))\n",
    "            dp[i] = d[-1][0] + nums[i]\n",
    "            d.add((dp[i], i))\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "import sys\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        q=[[-1*nums[0],0]]\n",
    "        ans=nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            while(q):\n",
    "                pre,j=heapq.heappop(q)\n",
    "                if i-j<=k:\n",
    "                    heapq.heappush(q,[pre,j])\n",
    "                    break\n",
    "            ans=nums[i]-q[0][0]\n",
    "            heapq.heappush(q,[-1*ans,i])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int: # dp+最大堆\n",
    "        n = len(nums)\n",
    "        max_f = []\n",
    "        ans = nums[0]\n",
    "        heappush(max_f, (-nums[0], 0))\n",
    "\n",
    "        for i in range(1, n):\n",
    "            while max_f and i - max_f[0][1] > k:\n",
    "                heappop(max_f)\n",
    "\n",
    "            ans = -max_f[0][0] + nums[i]\n",
    "            heappush(max_f, (-ans, i))\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # n = len(nums)\n",
    "        # max_f = []\n",
    "        # heapify(max_f)\n",
    "        # heappush(max_f, (-nums[0], 0))\n",
    "        # ans = nums[0]\n",
    "        # for i in range(1, n):\n",
    "        #     while max_f and i - max_f[0][1] > k:\n",
    "        #         heappop(max_f)\n",
    "        #     ans = -max_f[0][0] + nums[i]\n",
    "        #     heappush(max_f, (-ans, i))\n",
    "\n",
    "        # return ans\n",
    "\n",
    "\n",
    "\n",
    "nums = [1,-5,-20,4,-1,3,-6,-3]\n",
    "k = 2\n",
    "c = Solution()\n",
    "print(c.maxResult(nums, k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int: # dp+最大堆\n",
    "        n = len(nums)\n",
    "        max_f = []\n",
    "        ans = nums[0]\n",
    "        heappush(max_f, (-ans, 0))\n",
    "\n",
    "        for i in range(1, n):\n",
    "            while max_f and i - max_f[0][1] > k:\n",
    "                heappop(max_f)\n",
    "\n",
    "            ans = -max_f[0][0] + nums[i]\n",
    "            heappush(max_f, (-ans, i))\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # n = len(nums)\n",
    "        # max_f = []\n",
    "        # heapify(max_f)\n",
    "        # heappush(max_f, (-nums[0], 0))\n",
    "        # ans = nums[0]\n",
    "        # for i in range(1, n):\n",
    "        #     while max_f and i - max_f[0][1] > k:\n",
    "        #         heappop(max_f)\n",
    "        #     ans = -max_f[0][0] + nums[i]\n",
    "        #     heappush(max_f, (-ans, i))\n",
    "\n",
    "        # return ans\n",
    "\n",
    "\n",
    "\n",
    "nums = [1,-5,-20,4,-1,3,-6,-3]\n",
    "k = 2\n",
    "c = Solution()\n",
    "print(c.maxResult(nums, k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        maxHeap = []\n",
    "        heapq.heapify(maxHeap)\n",
    "        heapq.heappush(maxHeap, (-nums[0], 0) )\n",
    "        res = nums[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            while maxHeap and i - maxHeap[0][1] > k:    #index的距离太大，以后i越来越大，top()就没用了\n",
    "                heapq.heappop(maxHeap)\n",
    "            res = -maxHeap[0][0] + nums[i]\n",
    "            heapq.heappush(maxHeap, (-res, i) )         #dp的思想\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "      if k == 1:\n",
    "        return sum(nums)\n",
    "      t = -nums[0]\n",
    "      h = [(t, 0)]\n",
    "      for i in range(1, len(nums)):\n",
    "        j = i - k\n",
    "        while h[0][1] < j:\n",
    "          heappop(h)\n",
    "        t = h[0][0] - nums[i]\n",
    "        heappush(h, (t, i))\n",
    "      return -t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        q = []\n",
    "        n = len(nums)\n",
    "        heappush(q, (-nums[0], 0))\n",
    "        ans = nums[0]\n",
    "        for i in range(1, n):\n",
    "            x = nums[i]\n",
    "            while q and q[0][1] + k < i:\n",
    "                heappop(q)\n",
    "            ans = -q[0][0] + x\n",
    "            heappush(q, (-ans, i))\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n \n",
    "        dp[0] = nums[0]\n",
    "        heap = []\n",
    "        heapq.heappush(heap, (-nums[0], 0))\n",
    "        for i in range(1, n):\n",
    "            if heap:\n",
    "                while i - heap[0][1] > k:\n",
    "                    heapq.heappop(heap)\n",
    "                val = -heap[0][0]\n",
    "                dp[i] = nums[i] + val\n",
    "                heapq.heappush(heap, (-dp[i], i))\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        # f[i]: 到达位置i时的可获得的最大得分\n",
    "        # 动态规划: f[i] = max{f[i-j]} + nums[i], 其中j=1,2,..,k\n",
    "        n = len(nums)\n",
    "        f = nums[:]\n",
    "        q = [(-nums[0], 0)]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            while i - q[0][1] > k:\n",
    "                heapq.heappop(q)\n",
    "            f[i] = nums[i] - q[0][0]\n",
    "            heapq.heappush(q, (-f[i], i))\n",
    "\n",
    "        return f[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        nums_length = len(nums)\n",
    "        score = [0] * nums_length\n",
    "        heap = list()\n",
    "        score[0] = nums[0]\n",
    "\n",
    "        for i in range(1, nums_length):\n",
    "            heapq.heappush(heap, (-score[i-1], i-1))\n",
    "            while heap[0][1] < (i - k):\n",
    "                heapq.heappop(heap)\n",
    "            score[i] = -heap[0][0] + nums[i]\n",
    "        \n",
    "        return score[nums_length-1]\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        # dp[i]表示以nums[i]结尾的最大得分\n",
    "        # dp[i]=max(dp[i-1],...,dp[i-k])+nums[i],求出任意时刻前k个位置的最大值，pq或者mq\n",
    "        n=len(nums)\n",
    "        dp=[-inf]*n\n",
    "        pq=PriorityQueue()\n",
    "        dp[0]=nums[0]\n",
    "        pq.put((-nums[0],0))\n",
    "        for i in range(1,n):\n",
    "            while not pq.empty() and pq.queue[0][1]<i-k:pq.get()\n",
    "            dp[i]=-pq.queue[0][0]+nums[i]\n",
    "            pq.put((-dp[i],i))                \n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = nums[:]\n",
    "        q = []\n",
    "        for i in range(1,n):\n",
    "            heappush(q,(-dp[i-1],i-1))\n",
    "            while q[0][1]<i-k:\n",
    "                heappop(q)\n",
    "            dp[i] = -q[0][0]+dp[i]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        q = [(-nums[0], 0)]\n",
    "        n = len(nums)\n",
    "        heapq.heapify(q)\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            while q and q[0][1] < i - k:\n",
    "                heapq.heappop(q)\n",
    "            dp[i] = dp[q[0][1]] + nums[i]\n",
    "            heapq.heappush(q, (-dp[i], i))\n",
    "        return dp[n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        heap = [] \n",
    "        L = len(nums)\n",
    "\n",
    "        for idx in range(L): \n",
    "            while len(heap) > 0 and heap[0][1] < idx - k:\n",
    "                heapq.heappop(heap) \n",
    "            \n",
    "            prev_max = 0 \n",
    "            if len(heap) > 0: \n",
    "                prev_max -= heap[0][0] \n",
    "\n",
    "            nums[idx] += prev_max \n",
    "            heapq.heappush(heap, [-nums[idx], idx]) \n",
    "\n",
    "        return nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        last = [[-nums[0], 0]]\n",
    "        cur = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            while i - last[0][1] > k:\n",
    "                heapq.heappop(last)\n",
    "            if i==len(nums)-1:\n",
    "                return -(last[0][0]-nums[i])\n",
    "            heapq.heappush(last, [last[0][0]-nums[i], i])\n",
    "        return nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        heap = []\n",
    "        heapq.heappush(heap, [-nums[0], 0])\n",
    "        for i in range(1, len(nums) - 1):                \n",
    "            heapq.heappush(heap, [-nums[i] + heap[0][0], i])\n",
    "            while heap[0][1] <= i-k:\n",
    "                heapq.heappop(heap)\n",
    "        return nums[-1] - heap[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        st = []\n",
    "        for i, num in enumerate(nums):\n",
    "            if i == 0:\n",
    "                if i == len(nums) - 1:\n",
    "                    return num\n",
    "                heapq.heappush(st, [-num, i])\n",
    "                continue\n",
    "            while st and st[0][1] < i - k:\n",
    "                heapq.heappop(st)\n",
    "            cur = -st[0][0] + num\n",
    "            if i == len(nums) - 1:\n",
    "                return cur\n",
    "            heapq.heappush(st, [-cur, i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        L = len(nums)\n",
    "        dp = [0] * L\n",
    "        dp[0] = nums[0]\n",
    "        pq = [[-dp[0], 0]]\n",
    "        for i in range(1, L):\n",
    "            while pq[0][1] < i - k:\n",
    "                heappop(pq)\n",
    "            dp[i] = nums[i] - pq[0][0]\n",
    "            heappush(pq, [-dp[i], i])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        q = []\n",
    "        heapq.heapify(q)\n",
    "        heapq.heappush(q, [-nums[0], 0])\n",
    "        res = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            while q and i - q[0][1] > k:\n",
    "                heapq.heappop(q)\n",
    "            res = -q[0][0] + nums[i]\n",
    "            heapq.heappush(q,[-res, i])\n",
    "        print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        q = [[-nums[0], 0]]\n",
    "        heapq.heapify(q)\n",
    "        res = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            while q and i - q[0][1] > k:\n",
    "                heapq.heappop(q)\n",
    "            res = -q[0][0]+nums[i]\n",
    "            heapq.heappush(q, [-res, i])\n",
    "        print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        hp = [[-nums[0], 0]]  # 堆\n",
    "        dp = nums[0]\n",
    "        for i in range(1, n):\n",
    "            while len(hp) > 0 and i - hp[0][1] > k:\n",
    "                heappop(hp)\n",
    "            x, j = hp[0]\n",
    "            dp = -x + nums[i]   # 到达 nums[i] 的最大得分\n",
    "            heappush(hp, [-dp, i])\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = nums[:]\n",
    "        heap = [(-dp[0], 0)]\n",
    "        for i in range(1, n):\n",
    "            while heap:\n",
    "                value, index = heapq.heappop(heap)\n",
    "                if index + k < i:\n",
    "                    continue\n",
    "                dp[i] = nums[i] - value\n",
    "                heapq.heappush(heap, (-dp[i], i))\n",
    "                heapq.heappush(heap, (value, index))\n",
    "                break\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        h=[];n=len(nums);dp=[nums[0]]*n\n",
    "        for i  in range(1,n):\n",
    "            heappush(h,(-dp[i-1],i-1));\n",
    "            while h[0][1]<i-k:heappop(h)\n",
    "            dp[i]=-h[0][0]+nums[i]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        dp = [float(-inf)]*len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        max_heap = []\n",
    "        heapq.heappush(max_heap,(-nums[0],0))\n",
    "        \n",
    "        for i in range(1,len(nums)):\n",
    "            while max_heap[0][1]<i-k:\n",
    "                heapq.heappop(max_heap)\n",
    "            dp[i] = nums[i] - max_heap[0][0]\n",
    "            heapq.heappush(max_heap,(-dp[i],i))\n",
    "            \n",
    "        \n",
    "        #print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n \n",
    "        dp[0] = nums[0]\n",
    "        heap = []\n",
    "        heapq.heappush(heap, (-nums[0], 0))\n",
    "        for i in range(1, n):\n",
    "            if heap:\n",
    "                while i - heap[0][1] > k:\n",
    "                    heapq.heappop(heap)\n",
    "                val = -heap[0][0]\n",
    "                dp[i] = nums[i] + val\n",
    "                heapq.heappush(heap, (-dp[i], i))\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n \n",
    "        dp[0] = nums[0]\n",
    "        heap = []\n",
    "        heapq.heappush(heap, (-nums[0], 0))\n",
    "        for i in range(1, n):\n",
    "            if heap:\n",
    "                while i - heap[0][1] > k:\n",
    "                    heapq.heappop(heap)\n",
    "                val = -heap[0][0]\n",
    "                dp[i] = nums[i] + val\n",
    "                heapq.heappush(heap, (-dp[i], i))\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxResult(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n \n",
    "        dp[0] = nums[0]\n",
    "        heap = []\n",
    "        heapq.heappush(heap, (-nums[0], 0))\n",
    "        for i in range(1, n):\n",
    "            if heap:\n",
    "                while i - heap[0][1] > k:\n",
    "                    heapq.heappop(heap)\n",
    "                val = -heap[0][0]\n",
    "                dp[i] = nums[i] + val\n",
    "                heapq.heappush(heap, (-dp[i], i))\n",
    "        return dp[-1]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
